#ifndef __DYNAMICARRAY_H_
#define __DYNAMICarray_H_

#include <cstddef>
#include <limits.h>
#include "student.h"

using ElementType = void *;

class DynamicArray
{
public:
    DynamicArray();
    DynamicArray(const DynamicArray &a);
    DynamicArray &operator=(const DynamicArray &a);
    ~DynamicArray();

    void SetFreeFunc(void (*Free)(void *))
    {
        this->Free = Free;
    }

    void SetPrintFunc(void (*print)(void *))
    {
        this->print = print;
    }

    void SetComprFunc(int (*compare)(void *,void *))
    {
       this->compare = compare;
    }

    void SetComprFunc(bool (*AllCompare)(void *,void *))
    {
       this->AllCompare = AllCompare;
    }

    void SetCopyFunc(void (*Copy)(void *,void *))
    {
        this->Copy = Copy;
    }

    // 插入
    // 尾插法:在size的位置插入
    void InsertTail(const ElementType &element);
    // 头插法： 在第一个位置插入
    void InsertHead(const ElementType &element);
    // 中间插入
    void InsertByIndex(const ElementType &element, size_t index);

    // 删除
    // 按位置删除
    void RemoveByIndex(size_t index);
    // 按值删除
    void RemoveByElement(const ElementType &element);

    // 查找
    // 按位置查找
    ElementType *FindByIndex(size_t index); // 返回指针 空和非空
    // 按值查找
    // 返回下标的集合
    DynamicArray FindByElement(const ElementType &element); // 返回数组

    // 修改
    void UpdateByIndex(size_t index, const ElementType &newValue);
    void UpdateByElement(const ElementType &element, const ElementType &newValue);

    ElementType &operator[](int index); // 查找和修改统一在一个接口里  不能判断非法值(只有指针可以判断非法值) 且不能判断越界

    // 排序算法
    void Sort();
    // 去重算法
    void Duplicate();
    // 合并:两个有序数列合并成一个新的有序数列
    DynamicArray Merge(const DynamicArray &a);
    // 取交集
    DynamicArray FdIntrSctn(const DynamicArray &a);
    // 取并集
    DynamicArray FindUnionSet(const DynamicArray &a);
    // 取补集
    DynamicArray FindDifference(const DynamicArray &a);

    // 判断两个数列是否相等
    bool operator==(const DynamicArray &a);

    // 二分法 没找到返回ULONMG_MAX
    size_t BinarySearch(const ElementType &element);
    // 判断一个数列是不是另一个数列的子数列
    bool Contains(const DynamicArray &a);
    // 判断一个数列是不是连续子序列
    bool ContnsContains(const DynamicArray &a);
    // 获取子序列
    DynamicArray SubSquence(size_t index, size_t len);

    void show();

private:
    size_t partition(size_t start, size_t end);
    void FastSort(size_t start, size_t end, size_t CurDepth, size_t MaxDepth); // 一个最大的递归深度，防止爆栈
    void InsertSort(size_t start, size_t end);
    void ReSize(size_t capacity);
    ElementType *array;
    size_t capacity; // unsigned long
    size_t size;

    void (*Free)(void *);            // 释放对象的函数指针
    int (*compare)(void *, void *); // 比较大小的指针
    bool (*AllCompare)(void *, void *);
    void (*print)(void *);           // 打印
    void (*Copy)(void*,void *);
};

#endif
